Quando alguns trens de passageiros chegam ao fim da linha, eles precisam ir até uma plataforma de baldeação para serem redirecionados e poderem partir da estação mais tarde, geralmente de uma plataforma diferente daquela em que chegaram.

Os engenheiros usam programas de software chamados solucionadores algorítmicos para planejar esses movimentos, mas em uma estação com milhares de chegadas e partidas semanais, o problema se torna complexo demais para um solucionador tradicional resolver tudo de uma vez.

Utilizando aprendizado de máquina, pesquisadores do MIT desenvolveram um sistema de planejamento aprimorado que reduz o tempo de resolução em até 50% e produz uma solução que atende melhor aos objetivos do usuário, como partidas de trens pontuais. O novo método também pode ser usado para resolver com eficiência outros problemas logísticos complexos, como escalonamento de equipes de hospitais, designação de equipes de companhias aéreas ou atribuição de tarefas a máquinas de fábrica.

Engenheiros frequentemente dividem esses tipos de problemas em uma sequência de subproblemas sobrepostos, cada um dos quais pode ser resolvido em um período de tempo viável. Mas as sobreposições fazem com que muitas decisões sejam recomputadas desnecessariamente, levando o solucionador a levar muito mais tempo para chegar a uma solução ótima.

A nova abordagem, aprimorada por inteligência artificial, aprende quais partes de cada subproblema devem permanecer inalteradas, congelando essas variáveis para evitar cálculos redundantes. Em seguida, um solucionador algorítmico tradicional lida com as variáveis restantes.

“Muitas vezes, uma equipe dedicada pode passar meses ou até anos projetando um algoritmo para resolver apenas um desses problemas combinatórios. O aprendizado profundo moderno nos dá a oportunidade de usar novos avanços para ajudar a otimizar o design desses algoritmos. Podemos pegar o que sabemos que funciona bem e usar a IA para acelerá-lo”, afirma Cathy Wu, Professora Associada de Desenvolvimento de Carreira Thomas D. e Virginia W. Cabot em Engenharia Civil e Ambiental (CEE) e no Instituto de Dados, Sistemas e Sociedade (IDSS) do MIT, e membro do Laboratório de Sistemas de Informação e Decisão (LIDS).

Ela é acompanhada no artigo pela autora principal, Sirui Li, aluna de pós-graduação do IDSS; Wenbin Ouyang, aluna de pós-graduação do CEE; e Yining Ma, pós-doutoranda do LIDS. A pesquisa será apresentada na Conferência Internacional sobre Representações de Aprendizagem.

Uma motivação para esta pesquisa é um problema prático identificado pelo aluno de mestrado Devin Camille Wilkins no curso de transporte de nível básico de Wu. O aluno queria aplicar o aprendizado por reforço a um problema real de despacho de trens na Estação Norte de Boston. A organização de transporte precisa alocar muitos trens a um número limitado de plataformas, onde possam ser desviados com bastante antecedência de sua chegada à estação.

Isso acaba sendo um problema de agendamento combinatório muito complexo — o tipo exato de problema no qual o laboratório de Wu passou os últimos anos trabalhando.

Quando confrontados com um problema de longo prazo que envolve a atribuição de um conjunto limitado de recursos, como tarefas de fábrica, a um grupo de máquinas, os planejadores geralmente enquadram o problema como Programação Flexível de Oficina.

No Agendamento Flexível de Job Shop, cada tarefa precisa de um tempo diferente para ser concluída, mas pode ser atribuída a qualquer máquina. Ao mesmo tempo, cada tarefa é composta de operações que devem ser executadas na ordem correta.

Esses problemas rapidamente se tornam muito grandes e difíceis de manejar para os solucionadores tradicionais, então os usuários podem empregar a otimização de horizonte móvel (RHO) para dividir o problema em partes gerenciáveis que podem ser resolvidas mais rapidamente.

Com o RHO, um usuário atribui algumas tarefas iniciais a máquinas em um horizonte de planejamento fixo, talvez uma janela de tempo de quatro horas. Em seguida, ele executa a primeira tarefa dessa sequência e avança o horizonte de planejamento de quatro horas para adicionar a próxima tarefa, repetindo o processo até que todo o problema seja resolvido e o cronograma final de atribuições de tarefas por máquina seja criado.

O horizonte de planejamento deve ser maior que a duração de qualquer tarefa, pois a solução será melhor se o algoritmo também considerar as tarefas que surgirão.

Mas, à medida que o horizonte de planejamento avança, isso cria alguma sobreposição com as operações do horizonte de planejamento anterior. O algoritmo já apresentou soluções preliminares para essas operações sobrepostas.

Para sua técnica, que eles chamam de otimização de horizonte rolante guiada por aprendizagem (L-RHO), os pesquisadores ensinam um modelo de aprendizado de máquina para prever quais operações, ou variáveis, devem ser recomputadas quando o horizonte de planejamento avança.

O L-RHO requer dados para treinar o modelo, então os pesquisadores resolveram um conjunto de subproblemas usando um solucionador algorítmico clássico. Eles pegaram as melhores soluções — aquelas com o maior número de operações que não precisam ser recomputadas — e as usaram como dados de treinamento.

Uma vez treinado, o modelo de aprendizado de máquina recebe um novo subproblema nunca visto antes e prevê quais operações não devem ser recomputadas. As operações restantes são realimentadas para o solucionador algorítmico, que executa a tarefa, recomputa essas operações e move o horizonte de planejamento para a frente. Em seguida, o ciclo recomeça.

"Se, em retrospectiva, não precisássemos reotimizá-las, poderíamos remover essas variáveis do problema. Como esses problemas crescem exponencialmente, pode ser bastante vantajoso eliminar algumas dessas variáveis", acrescenta.

Para testar sua abordagem, os pesquisadores compararam o L-RHO a diversos solucionadores algorítmicos básicos, solucionadores especializados e abordagens que utilizam apenas aprendizado de máquina. O desempenho foi superior a todos eles, reduzindo o tempo de resolução em 54% e melhorando a qualidade da solução em até 21%.

Além disso, o método continuou a superar todas as linhas de base quando testado em variantes mais complexas do problema, como quando máquinas de fábrica quebram ou quando há congestionamento adicional de trens. Ele superou até mesmo linhas de base adicionais que os pesquisadores criaram para desafiar seu solucionador.

“Nossa abordagem pode ser aplicada sem modificações a todas essas variantes diferentes, que é realmente o que pretendemos fazer com esta linha de pesquisa”, diz ela.

O L-RHO também pode se adaptar se os objetivos mudarem, gerando automaticamente um novo algoritmo para resolver o problema — tudo o que ele precisa é de um novo conjunto de dados de treinamento.

No futuro, os pesquisadores querem entender melhor a lógica por trás da decisão do modelo de congelar algumas variáveis, mas não outras. Eles também querem integrar sua abordagem a outros tipos de problemas complexos de otimização, como gestão de estoque ou roteirização de veículos.

Este trabalho foi apoiado, em parte, pela National Science Foundation, pelo Comitê de Apoio à Pesquisa do MIT, por uma bolsa de doutorado da Amazon Robotics e pela MathWorks.